<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4746：[Usaco2016 Dec]Lasers and Mirrors</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2016 Dec]Lasers and Mirrors</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2016 Dec]Lasers and Mirrors</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2016 Dec]Lasers and Mirrors                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>
<div>For some reason, Farmer John's cows always seem to be running laser light shows.For their latest sho</div>
<div>w, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move</div>
<div>&nbsp;it easily from the location where it was delivered. They would like to somehow send the light from&nbsp;</div>
<div>the laser to the barn on the other side of FJ's property. Both the laser and the barn can be conside</div>
<div>red to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser&nbsp;</div>
<div>so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or&nbsp;</div>
<div>y axes). They will then bounce this beam off a number of mirrors to direct it to the barn.On the far</div>
<div>m there are N fence posts (1&le;N&le;100,000) located at distinct 2D points (also distinct from the lase</div>
<div>r and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror on a&nbsp;</div>
<div>fence post, in which case the laser would simply pass straight over the top of the post without chan</div>
<div>ging direction. If the cows do mount a mirror on a fence post, they align it diagonally like / or \&nbsp;</div>
<div>so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.Please co</div>
<div>mpute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to</div>
<div>&nbsp;the barn.</div>
<div>出于某种原因，农夫约翰的奶牛总是喜欢使用激光。奶牛们搞到了一个强大的激光发射器，它很重，所以不能移动</div>
<div>它的位置。奶牛想用它照射到约翰的谷仓的另一端。众所周知，光沿直线传播，所以必须通过镜子的反射来使光线</div>
<div>发生偏折。激光射出的方向只能是平行于x轴或y轴的。农场上有N（1&lt;=N&lt;=100000）个坑位于平面直角坐标系上的</div>
<div>不同点（和激光发射器的位置和目标点的位置也不相同）。奶牛可以把镜子安装在坑里（当然也可以不安）。镜子</div>
<div>可以摆成&ldquo;/&rdquo;或者&ldquo;\&rdquo;。由物理知识可以知道，一道平行于x轴的光射到镜子上一定会平行于y轴射出，平行于y</div>
<div>轴的光一定会平行于x轴射出。现在给你激光发射器的坐标、目标点的坐标和所有坑的坐标，请你用最少的镜子来</div>
<div>实现奶牛的梦想。</div>
</div>
<div></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line of input contains 5 space-separated integers: N,xL,yL,xB,yB&nbsp;</div>
<div>where (xL,yL) is the location of the laser and (xB,yB) is the location of the barn.&nbsp;</div>
<div>All coordinates are between 0 and 1,000,000,000</div>
<div>The next N lines each contain the xx and y locations of a fence post,</div>
<div>both integers in the range 0&hellip;1,000,000,000</div>
<div><span style="font-family: arial, verdana, helvetica, sans-serif;">第一行包含5个正整数，分别是N,x1,y1,x2,y2，N的意义如题所述，(x1,y1)为激光发射器的坐标，(x2,y2)为目标点的坐标。</span><br style="font-family: arial, verdana, helvetica, sans-serif;" />
<span style="font-family: arial, verdana, helvetica, sans-serif;">0&lt;=x1,y1,x2,y2&lt;=1,000,000,000</span><br style="font-family: arial, verdana, helvetica, sans-serif;" />
<span style="font-family: arial, verdana, helvetica, sans-serif;">接下来N行，每行两个整数x,y表示坑的坐标。</span><br style="font-family: arial, verdana, helvetica, sans-serif;" />
<span style="font-family: arial, verdana, helvetica, sans-serif;">0&lt;=x,y&lt;=1,000,000,000</span></div>
<div></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>output the minimum number of mirrors needed to direct the laser to the barn,</div>
<div>
<div>or -1 if this is impossible to do.</div>
<div><span style="font-family: arial, verdana, helvetica, sans-serif;">最少安装多少个镜子。如果无论怎样都无法完成，输出-1。</span></div>
<div></div>
</div>
<p></p></p><hr/><h3>样例输入</h3><pre>4 0 0 7 2
3 2
0 2
1 6
3 0</pre><hr/><h3>样例输出</h3><pre>1</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Gold</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4746" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4746" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>